package cluster;

import java.io.*;
import java.util.ArrayList;
import java.util.Random;
import util.PicUtility;

public class k_means {
    ArrayList<double[]>dataSet;
    int clusterNum;
    int dim;
    k_means(int clusterNum){
        this.clusterNum=clusterNum;
        dataSet=new ArrayList<double[]>();
    }

    //data load dataSet
    public void loadDataSet(String filePath){
        File file=new File(filePath);
        FileReader fr;
        try{
            fr=new FileReader(file);
            BufferedReader bis=new BufferedReader(fr);
            String line=null;
            while((line=bis.readLine())!=null){
                String[]str=line.trim().split(" ");
                double[] data=new double[str.length];
                for(int i=0;i<data.length;i++){
                    data[i]=Double.parseDouble(str[i]);
                }
                dataSet.add(data);
            }
            dim=dataSet.get(0).length;
            bis.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void cluster(){
        Random rand=new Random();
        double [][]clusterMeans=new double[clusterNum][dim];
        for(int n=0;n<clusterNum;n++){
            double[] data=new double[dim];
            for(int m=0;m<dim;m++){
                data[m]=rand.nextDouble()*100;
            }
            clusterMeans[n]=data;
        }
        boolean isContinue=true;
        while(isContinue){
            isContinue=false;
            double[][] nextClusterMeans=new double[clusterNum][dim];
            int []clusterDataNum=new int[clusterNum];
            for(int n=0;n<dataSet.size();n++){
                double minDis=Double.MAX_VALUE;
                int whoCluster=-1;
                for(int m=0;m<clusterNum;m++){
                    double distance=this.getDist(clusterMeans[m],dataSet.get(n));
                    if(distance<minDis){
                        whoCluster=m;
                        minDis=distance;
                    }
                }
                clusterDataNum[whoCluster]++;
                for(int i=0;i<dim;i++){
                    nextClusterMeans[whoCluster][i]+=dataSet.get(n)[i];
                }
            }
            for(int i=0;i<clusterNum;i++){
                for(int j=0;j<dim;j++){
                    if(clusterDataNum[i]!=0){
                        nextClusterMeans[i][j]/=clusterDataNum[i];
                    }else{
                        nextClusterMeans[i][j]=Math.random()*100;
                    }
                }
            }
            for(int i=0;i<clusterNum;i++){
                if(this.getDist(nextClusterMeans[i],clusterMeans[i])!=0){
                    isContinue=true;
                }
            }
            clusterMeans=nextClusterMeans;
        }

        //visualization
        ArrayList<ArrayList<double[]>>clusters=new ArrayList<ArrayList<double[]>>();
        for(int n=0;n<clusterNum;n++){
            clusters.add(new ArrayList<double[]>());
        }
        for(int n=0;n<dataSet.size();n++){
            double minDis=Double.MAX_VALUE;
            int whoCluster=-1;
            for(int m=0;m<clusterNum;m++){
                double distance=this.getDist(clusterMeans[m],dataSet.get(n));
                if(distance<minDis){
                    whoCluster=m;
                    minDis=distance;
                }
            }
            clusters.get(whoCluster).add(dataSet.get(n));
        }
        double [][][]datas=new double[clusterNum][][];
        for(int n=0;n<clusterNum;n++){
            double[][]cluster=new double[clusters.get(n).size()][];
            for(int m=0;m<cluster.length;m++){
                cluster[m]=clusters.get(n).get(m);
            }
            datas[n]=cluster;
        }
        System.out.println("cluster mean:");
        for(int n=0;n<clusterMeans.length;n++){
            for(double x : clusterMeans[n]){
                System.out.print(x+" ");
            }
            System.out.println();
        }

        PicUtility.show(datas, clusterNum);
    }

    private double getDist(double[]test,double[]data){
        double sum=0;
        for(int n=0;n<test.length;n++){
            sum+=(test[n]-data[n])*(test[n]-data[n]);
        }
        return Math.sqrt(sum);
    }

    public static void main(String args[]){
        k_means kmean=new k_means(3);
        kmean.loadDataSet("/home/tang/data.txt");
        kmean.cluster();
    }
}
